// 随机快速排序，acm练习风格
// 测试链接 : https://www.luogu.com.cn/problem/P1177
#include<iostream>
#include<vector>
#include<time.h>
#include<map>
using namespace std;
//优化版本 划分三路
pair<int,int> partition2(vector<int>&arr,int left,int right,int x)
{
        int i=left,j=right,k=left;
        while(k<=j)//循环终止条件为什么不等于呢？可以这样想j的右边全是大于x的
        //j的位置是收货的位置，当k<j时此时k这个货物还有可能发送到j;如果k与j相等说明不需要发收货了
        {
            //这个是逆序
            if(arr[k]>x) swap(arr[k++],arr[i++]);
            else if(arr[k]==x) k++;
            else  swap(arr[k],arr[j--]);
        }
        return {i,j};
}
//经典版
int partition1(vector<int>&arr,int left,int right,int x)
{
    int xi=0;
    int j=left;
    for(int i=left;i<=right;i++)//利用快慢指针把<=x的换到j位置
    {
        if(arr[i]<=x) 
        {
            swap(arr[j],arr[i]);
            if(arr[j]==x) xi=j;//记录换位之后x的下标方便把x放到中间
            j++;
        }
    }
    swap(arr[xi],arr[j-1]);
    return j-1;
}
void quicksort(vector<int>&arr,int left,int right)
{
    if(left>=right) return;
    srand((unsigned int)time(nullptr));
    int index=left+(rand()%(right-left+1));
    int x=arr[index];
   // int mid=partition1(arr,left,right,x);//负责把x的左边为<=x，右边>x返回中间下标
   int mid1=partition2(arr,left,right,x).first;
   int mid2=partition2(arr,left,right,x).second;
    quicksort(arr,left,mid1-1);
    quicksort(arr,mid2+1,right);
}
int main()
{
    int n;cin>>n;
    vector<int>arr(n);
    for(auto&ch:arr) cin>>ch;
    quicksort(arr,0,n-1);
    for(auto&ch:arr)cout<<ch<<" ";
    return 0;
}